import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2024-02-22
 * Time: 23:34
 */
public class TestDeque {
    // 有效括号序列
    public boolean isValid(String s) {
        Deque<Character> stack1 = new LinkedList<>();

        // write code here
        int i;
        for (i = 0; i < s.length(); i++) {
            char tmp = s.charAt(i);
            // 思路：将期待序列放到栈中（括号匹配天生适用于栈）
            if (tmp == '(') {
                stack1.push(')');
            } else if (tmp == '[') {
                stack1.push(']');
            } else if (tmp == '{') {
                stack1.push('}');
            } else {
                if (stack1.isEmpty() || stack1.pop() != tmp) {
                    return false;
                }
            }
        }
        // 如果上面没返回false，结果取决于栈中是否还有元素
        return stack1.isEmpty();
    }

    // 寻找第k大（快排思想）（当前是允许重复，如果不允许重复呢？）
    public int findKth(int[] a, int n, int K) {
        // write code here
        int res = quickSort(a, 0, n - 1, K - 1);
        return res;

    }

    private int quickSort(int[] a, int left, int right, int k) {

        int pivot = partition(a, left, right);
        if (k == pivot) {
            return a[pivot];
        } else if (pivot < k) {
            return quickSort(a, pivot + 1, right, k);
        } else {
            return quickSort(a, left, pivot - 1, k);
        }
    }

    private int partition(int[] a, int left, int right) {
        int i = left;
        while (left < right) {
            // 让right下标指向右边大于tmp的值
            while (left < right && a[right] <= a[i]) {
                right--;
            }
            // 让left下标指向左边小于tmp的值
            while (left < right && a[left] >= a[i]) {
                left++;
            }
            // 交换
            swap(a, left, right);
        }
        swap(a, left, i);

        return left;
    }

    private void swap(int[] a, int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }


    // 滑动窗口最大值（这个比较有意思）
    public ArrayList<Integer> maxInWindows(int[] num, int size) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //窗口大于数组长度的时候，返回空
        if (size <= num.length && size != 0) {
            //双向队列
            ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
            //先遍历一个窗口
            for (int i = 0; i < size; i++) {
                //去掉比自己先进队列的小于自己的值
                while (!dq.isEmpty() && num[dq.peekLast()] < num[i])
                    dq.pollLast();
                dq.add(i);
            }
            //遍历后续数组元素
            for (int i = size; i < num.length; i++) {
                //取窗口内的最大值
                res.add(num[dq.peekFirst()]);
                while (!dq.isEmpty() && dq.peekFirst() < (i - size + 1))
                    //弹出窗口移走后的值
                    dq.pollFirst();
                //加入新的值前，去掉比自己先进队列的小于自己的值
                while (!dq.isEmpty() && num[dq.peekLast()] < num[i])
                    dq.pollLast();
                dq.add(i);
            }
            res.add(num[dq.pollFirst()]);
        }
        return res;
    }

    // 表达式求值，只能说，真的不简单！
    public int solve (String s) {
        // write code here
        s = s.trim();
        Deque<Integer> stack = new ArrayDeque<>();
        int number = 0;
        char sign = '+';
        char[] charArray = s.toCharArray();
        for (int i = 0, n = charArray.length; i < n; i++) {
            char c = charArray[i];
            if (c == ' ') {
                continue;
            }
            if (Character.isDigit(c)) {
                number = number * 10 + c - '0';
            }
            if (c == '(') {
                int j = i + 1;
                int counterPartition = 1;
                while (counterPartition > 0) {
                    if (charArray[j] == '(') {
                        counterPartition++;
                    }
                    if (charArray[j] == ')') {
                        counterPartition--;
                    }
                    j++;
                }
                number = solve(s.substring(i + 1, j - 1));
                i = j - 1;
            }
            if (!Character.isDigit(c) || i == n - 1) {
                if (sign == '+') {
                    stack.push(number);
                } else if (sign == '-') {
                    stack.push(-1 * number);
                } else if (sign == '*') {
                    stack.push(stack.pop() * number);
                } else if (sign == '/') {
                    stack.push(stack.pop() / number);
                }
                number = 0;
                sign = c;
            }
        }
        int ans = 0;
        while (!stack.isEmpty()) {
            ans += stack.pop();
        }
        return ans;
    }

    // 栈的压入，弹出序列
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int n = pushA.length;
        //辅助栈
        Stack<Integer> s = new Stack<>();
        //遍历入栈的下标
        int j = 0;
        //遍历出栈的数组
        for(int i = 0; i < n; i++){
            //入栈：栈为空或者栈顶不等于出栈数组
            while(j < n && (s.isEmpty() || s.peek() != popA[i])){
                s.push(pushA[j]);
                j++;
            }
            //栈顶等于出栈数组
            if(s.peek() == popA[i])
                s.pop();
                //不匹配序列
            else
                return false;
        }
        return true;
    }

    // 中缀表达式转逆波兰表达式
    // 定义运算符优先级
    private static final Map<Character, Integer> precedence = new HashMap<>();
    static {
        precedence.put('+', 1);
        precedence.put('-', 1);
        precedence.put('*', 2);
        precedence.put('/', 2);
        precedence.put('^', 3);
    }

    public static String infixToRPN(String infix) {
        StringBuilder output = new StringBuilder(); // 存放输出结果
        Stack<Character> stack = new Stack<>(); // 运算符栈

        for (char c : infix.toCharArray()) {
            if (Character.isDigit(c)) { // 如果是数字，直接输出
                output.append(c);
            } else if (c == '(') { // 如果是左括号，入栈
                stack.push(c);
            } else if (c == ')') { // 如果是右括号，将左括号之前的运算符全部输出
                while (!stack.isEmpty() && stack.peek() != '(') {
                    output.append(stack.pop());
                }
                if (!stack.isEmpty()) {
                    stack.pop(); // 弹出左括号
                }
            } else { // 如果是运算符
                while (!stack.isEmpty() && stack.peek() != '(' && precedence.get(c) <= precedence.get(stack.peek())) {
                    output.append(stack.pop()); // 将优先级高于等于当前运算符的运算符全部输出
                }
                stack.push(c);
            }
        }

        while (!stack.isEmpty()) { // 将剩余的运算符全部输出
            output.append(stack.pop());
        }

        return output.toString();
    }

    // 逆波兰表达式求值
    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String x:tokens) {
            if (!x.equals("+") && !x.equals("-") && !x.equals("*") && !x.equals("/")) {
                stack.push(Integer.parseInt(x));
            } else {
                int num1 = stack.pop();
                int num2 = stack.pop();
                switch (x) {
                    case "+":
                        stack.push(num2+num1);
                        break;
                    case "-":
                        stack.push(num2-num1);
                        break;
                    case "*":
                        stack.push(num2*num1);
                        break;
                    case "/":
                        stack.push(num2/num1);
                        break;
                }
            }
        }
        return stack.pop();
    }
}
